package com.itheima.leetcode.od.b.graph.unionfindset;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * <h3>城市聚集度</h3>
 * 一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。
 * <p>
 * 当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（Degree of Polymerization），DPi = max（城市群1的城市个数，城市群2的城市个数，…城市群m 的城市个数）。
 * <p>
 * 请找出地图上DP值最小的城市（即找到城市j，使得DPj = min(DP1,DP2 … DPn))
 * <p>
 * 提示：如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）
 * <p>
 * 提示：DPi的计算，可以理解为已知一棵树，删除某个节点后；生成的多个子树，求解多个子数节点数的问题。
 * <p>
 * 输入描述：
 * <p>
 * 每个样例：第一行有一个整数N，表示有N个节点。1 <= N <= 1000。
 * <p>
 * 接下来的N-1行每行有两个整数x，y，表示城市x与城市y连接。1 <= x,  y <= N
 * <p>
 * 输出描述：
 * <p>
 * 输出城市的编号。如果有多个，按照编号升序输出。
 * <p>
 * 示例1   输入输出示例仅供调试，后台判题数据一般不包含示例
 * <p>
 * 输入
 * <p>
 * 5
 * <p>
 * 1 2
 * <p>
 * 2 3
 * <p>
 * 3 4
 * <p>
 * 4 5
 * <p>
 * 输出
 * <p>
 * 3
 * <p>
 * 说明
 * <p>
 * 输入表示的是如下地图：
 * <p>
 * <p>
 * <p>
 * 对于城市3，切断通往3的所有道路后，形成2个城市群[（1，2），（4，5）]，其聚集度分别都是2。DP3 = 2。
 * <p>
 * 对于城市4，切断通往城市4的所有道路后，形成2个城市群[（1，2，3），（5）]，DP4 = max（3，1）= 3。
 * <p>
 * 依次类推，切断其它城市的所有道路后，得到的DP都会大于2，因为城市3就是满足条件的城市，输出是3。
 * <p>
 * 示例2   输入输出示例仅供调试，后台判题数据一般不包含示例
 * <p>
 * 输入
 * <p>
 * 6
 * <p>
 * 1 2
 * <p>
 * 2 3
 * <p>
 * 2 4
 * <p>
 * 3 5
 * <p>
 * 3 6
 * <p>
 * 输出
 * <p>
 * 2 3
 * <p>
 * 说明
 * <p>
 * 将通往2或者3的所有路径切断，最大城市群数量是3，其他任意城市切断后，最大城市群数量都比3大，所以输出2 3。
 */
public class UrbanAgglomerationDegree {
    public static void main(String[] args) {
        /*//处理输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n - 1; i++) {
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
        }*/

        int n = 6;
        int[][] arr = Arrays.stream("1 2\n2 3\n2 4\n3 5\n3 6".split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(n, arr));
    }

    public static String getResult(int n, int[][] arr) {
        int res = Integer.MAX_VALUE;
        int[] maxArray = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            UnionFindSet uf = new UnionFindSet(n);
            for (int j = 0; j < arr.length; j++) {
                if (arr[j][0] == i || arr[j][1] == i) {
                    continue;
                } else {
                    uf.union(arr[j][0] - 1, arr[j][1] - 1);
                }
            }
            maxArray[i] = uf.getMax();
            res = Math.min(res, maxArray[i]);
        }

        ArrayList<String> ans = new ArrayList<>();

        for (int i = 1; i < maxArray.length; i++) {
            if (res == maxArray[i]) {
                ans.add(String.valueOf(i));
            }
        }

        return ans.stream().collect(Collectors.joining(" "));
    }
}